package tree;


import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree<V extends Comparable<V>> {

    private Node<V> root = null;

    public void add(V obj) {
        if (obj == null) {
            throw new IllegalArgumentException("Element must not be null!");
        }
        root = add(root, obj);
    }

    private Node<V> add(Node<V> node, V data) {
        if (node == null) {
            return node = new Node<V>(data);
        } else {
            int cmp = data.compareTo(node.data);
            if (cmp < 0)
                node.left = add(node.left, data);
            else if (cmp > 0)
                node.right = add(node.right, data);
            return node;
        }
    }

    public int size() {
        return (size(root));
    }

    private int size(Node<V> node) {
        if (node == null)
            return 0;
        else {
            return (size(node.left) + 1 + size(node.right));

        }
    }

    public int depth() {
        return depth(root);
    }

    private int depth(Node<V> node) {
        if (node == null)
            return 0;
        else
            return 1 + Math.max(depth(node.left), depth(node.right));
    }

    public boolean contains(V obj) {
        if (obj == null) {
            throw new IllegalArgumentException();
        }
        return contains(root, obj);
    }

    private boolean contains(Node<V> node, V data) {
        if (node == null)
            return false;
        else if (data.compareTo(node.data) == 0)
            return true;
        else if (data.compareTo(node.data) < 0)
            return contains(node.left, data);
        else
            return contains(node.right, data);
    }

    public void remove(V data) {
        if (data == null) {
            throw new IllegalArgumentException("Element must not be null!");
        }
        root = remove(root, data);
    }

    private Node<V> remove(Node<V> node, V data) {
        if (node == null) {
            System.out
                    .println("Impossible to remove: element is not in the tree");
            return node;
        } else if (data.compareTo(node.data) < 0)
            node.left = remove(node.left, data);
        else if (data.compareTo(node.data) > 0)
            node.right = remove(node.right, data);
        else {
            if (node.left == null)
                return node.right;
            else if (node.right == null)
                return node.left;
            else {
                Node<V> tmp = new Node<V>(
                        getMinElementFormRightSubtree(node.right));
                tmp.right = remove(node.right, tmp.data);
                tmp.left = node.left;
                node = tmp;
            }
        }
        return node;
    }

    private V getMinElementFormRightSubtree(Node<V> node) {
        while (node.right != null)
            node = node.right;
        return node.data;
    }

    private boolean isLeaf(Node<V> node) {
        if (node.left == null && node.right == null) {
            return true;
        } else
            return false;
    }

    public void removeAll() {
        removeAll(root);
    }

    private void removeAll(Node<V> node) {
        if (node == null)
            return;
        if (node.left != null && isLeaf(node.left))
            node.left = null;
        else {
            removeAll(node.left);
        }
        if (node.right != null && isLeaf(node.right))
            node.right = null;
        else {
            removeAll(node.right);
        }
        root = null;

    }

    public void printTree() {
        printTree(root);
    }

    public void printTree(Node<V> node) {
        if (node != null) {
            System.out.print(node.data + "  ");
            printTree(node.left);
            printTree(node.right);
        }
    }

    public void printByLevel() {
        printByLevel(root);
    }

    public void printByLevel(Node<V> node) {
        Queue<Node<V>> queue = new LinkedList<Node<V>>();
        queue.add(node);
        int currentLevelCount = 1;
        int nextLevelCount = 0;
        System.out.println("Binary tree in level order: ");
        while (!queue.isEmpty()) {

            Node<V> n = queue.remove();

            System.out.print(n.data + " ");
            if (n.left != null) {
                queue.add(n.left);
                nextLevelCount++;
            }
            if (n.right != null) {
                queue.add(n.right);
                nextLevelCount++;
            }
            currentLevelCount--;
            if (currentLevelCount == 0) {
                System.out.println("");
                currentLevelCount = nextLevelCount;
                nextLevelCount = 0;
            }
        }
    }

}
